Data encryption systems can be used to ensure the security and/or authenticity of a data message. In security applications, a data encryption system can transform a message into an ideally undecipherable form. Once transformed, the message can be transmitted over an insecure medium without fear that it may be intercepted and understood. In authentication applications, all or a portion of a message can be encrypted using secret key information. If the message is altered or corrupted in transit, or a third party attempts to impersonate the sender, the receiver can detect this fact using a decryption operation.
As computer networks continue to proliferate, concerns about security and authenticity of network data grow correspondingly. Many networks can include links that are not secure, or that could be accessed by third parties with relative ease. It is therefore desirable to encrypt sensitive data before and/or as it is being transmitted across a network.
The many applications where data encryption can be desirable include virtual private networks (VPN), secure electronic mail, banking systems that include electronic funds transfer (EFT), and various “real-time” applications such as voice and/or video over a network, where sensitive data is transmitted. Such applications can have two, potentially conflicting goals: security of transmission and speed of transmission. Because encryption is computationally intensive, it is difficult and expensive to build systems that encrypt and decrypt data at very high speed. For a networking system in particular, it is desirable to process packets as they arrive (at “wirespeed”), and with higher and higher bandwidth links becoming common, wirespeed encryption processing is becoming increasingly challenging.
An example of a basic encryption system is set forth in FIG. 6. The encryption system includes an encryption circuit 600. The encryption circuit 600 can receive in each processing time period one 64-bit block of “plaintext” (Bi) and transform it into a corresponding 64-bit block of “ciphertext” (Ci). The index i increases in time as subsequent blocks of plaintext are fed into the system, so that in the first processing period B1 is transformed to corresponding C1, in the next period B2 is transformed to C2, etc. In the arrangement of FIG. 6, a plain text block can be encrypted according to a key (K). A key can be subsequently used to decrypt the ciphertext back into its original plaintext form. In a symmetric encryption system, the same key is used to encrypt a message is used to decrypt the message. In an asymmetric encryption system, the key used to encrypt a message is different from that used to decrypt the message.
An encryption circuit 600 can include an algorithm executed by a general or special purpose processor, a dedicated circuit, or some combination thereof.
FIG. 7 illustrates an example of an encryption circuit. The encryption circuit is designated by the general reference character 700, and is shown to include a series of cipher stages 702-1 to702-n. Each cipher stage (702-1 to702-n) performs one portion of an encryption function.
In the arrangement of FIG. 7, the delay introduced by the encryption circuit 700 is the latency L introduced by the signal propagation delay of the circuit.
FIG. 8 illustrates an example of a pipelined encryption circuit. The pipelined encryption circuit is designated by the general reference character 800, and includes a series of clocked cipher stages 802-1 to 802-n. Each clocked cipher stage (802-1 to 802-n) performs one portion of an encryption function, but passes its results into a subsequent stage according to a clock signal CLK. Consequently, each clocked cipher stage (802-1 to 802-n) can be conceptualized as including a combinational section (804-1 to 804-n) and a pipeline register (806-1 to 806-n).
We will use the notation f(m,x) to represent the output of stage 802-m when the 64-bit value x is input to that stage. Then, in the diagram stage 802-1 receives as input Bi and generates the output f(1, Bi). Stage 802-2 receives as input f(1, Bi) and generates the output f(2, f(1, Bi)). Similarly, each stage receives the output of the previous stage as its input. Thus, the output of the entire chain is f(n, f(n−1, f(n−2, . . . f(2, f(1, Bi)) . . . ))).
We define the further notation F(m, x) to be the output of the chain of stages 802-1 through 802-m, given the 64-bit value x input to the first stage. Thus, in the figure the output of stage 802-1 would be F(1, Bi), the output of stage 802-2 would be F(2, Bi), and so on, so that the output of stage 802-n would be F(n, Bi), which should correspond to the desired ciphertext Ci.
FIG. 8 illustrates how the cryptographic computation can be pipelined. Thus, pipelined cipher section 802-2 is shown to provide an output value F(2, Bi−2), at the same instant that pipelined cipher section 802-1 receives an input value Bi.
In the arrangement of FIG. 8, the delay introduced by the encryption circuit 800 is the latency L, where L=(n)T=n(1/F). Here n is the number of clocked staged in the encryption circuit 800, and T and F are the period and frequency of the CLK signal, respectively. An advantage of the arrangement of FIG. 8 is that while the encryption of a particular plain text block involves a latency L, one block can be encrypted each clock cycle, in a pipelined fashion.
While a pipelined encrypting arrangement can provide a high throughput, such an arrangement may not be conducive to particular commonly used encryption modes. For example, many popular encryption modes combine a previously encrypted ciphertext block (or value) with a newly arriving plaintext block. In particular, one type of encryption is “DES,” described in DES: Data Encryption Standard, FIPS PUB 46, National Bureau of Standards in 1977. DES describes a cyclic block chaining (CBC) mode in which a completed ciphertext block is exclusive-ORed (XORed) with a subsequent plaintext block in a data block series. DES also includes non-feedback modes. In an electronic codebook (ECB) mode, plaintext input blocks can be pipelined in serial fashion, without a feedback step.
An example of a CBC mode DES circuit is shown in FIG. 9. The circuit is designated by the general reference character 900 and is shown to receive a plaintext block (Bi). Block Bi is XORed, at XOR gate 902, with previously encrypted ciphertext block (Ci−1). This result will then be encrypted by encryption circuit 904 to form ciphertext block Ci, which is an output of the system, and which is also “fed back” as an input to the XOR gate 902 with plaintext block Bi+1, etc.
The encryption circuit of FIG. 9 has a latency shown as L. Thus, if a sequence of plaintext blocks is applied, the blocks must be spaced from one another by at least the latency L, since a new block cannot be processed by encryption circuit 904 until the ciphertext from the previous block has been fully computed. In a 3DES mode, a single block of plaintext data may be passed through encryption circuit 904 three times, before the ciphertext is available and the next plaintext block can be started.
In one particular arrangement, an encryption circuit 904 can include a number of DES rounds and provide a DES and/or 3DES type of encryption or decryption.
FIG. 10 sets forth an example of another encryption circuit that can include fewer cipher stages. The encryption circuit 1000 includes two cipher stages 1002-1 and 1002-2. Data can be processed through the cipher stages (1002-1 and 1002-2) multiple times to provide a desired encryption. For example, if an encryption operation required 16 cipher stages, a plain text block could be passed through cipher stages (1002-1 and 1002-2) eight times, with the output of 1002-2 passed back to the input of 1002-1. In the case of DES, the cipher stages 1002-1 and 1002-2 would use a different portion of the key K for each of the eight passes through them; a key schedule circuit, not shown, would be provided for this purpose. At the end of the eight passes through 1002-1 and 1002-2, a single ciphertext result would be obtained, and the next plaintext block could be started. The encryption circuit 1000 includes an XOR circuit 1006 for executing encryption functions that can require feeding encrypted data blocks back into newly received data blocks, such as DES and 3DES in CBC mode.
In light of the various applications for encryption circuits, only a few of which are mentioned above, there is a need for encryption systems that can process data blocks with higher throughput.
Other types of data operations can present problems which are similar in nature to encryption functions. For example, many operations can have “feedback” type steps, where a computed value is fed back into a computation stage as an operand. One particularly useful type of operation is modular exponentiation. In modular exponentiation, the computation can be reduced into a number of smaller multiplication and modular reduction steps, allowing for faster implementation on a computer or other hardware.
For example, it may be desirable to calculate the following:y=(Ae)mod n.Such a value can be reduced to a sequence of modulo n operations and multiplication operations. As just one example, the following method of calculating modular exponentiation can be implemented:
for (yy=1, aa=A, e!=0) {  if(e&1) yy=(yy*aa) mod n  aa=(aa*aa) mod n  e=e>>1}.
The step e&1 examines a particular bit of the value e. The step e=e>>1 moves to the next bit of e. The last value yy will be the desired result.
In this arrangement, the two operations yy=(yy*aa) mod n and aa=(aa*aa) mod n are computations that (apart from the first iteration) utilize the previously computed yy and aa results from the previous loop iteration. If such a computation is implemented in a pipelined circuit, and the latency of the circuit is greater than the rate at which values are applied to the circuit, each operation must “wait” until the previous result has fully propagated through the pipeline. This can result in delays and/or times at which various pipeline segments are idle.